package com.gjh.study.algorithm4.linked;

/**
 * 链表反转
 */
public class LinkedReverse<Item> {
    private class Node {
        Item item;
        Node next;
    }


    /**
     * 把原链表的头部，依次添加到反转链表的头部
     * @param x 原链表
     * @return 反转后的链表开头
     */
    public Node reverse(Node x) {
        // 当前链表的开头
        Node first = x;
        // 反转后的链表开头
        Node reverse = null;
        while (first != null) {
            // 当前节点头部节点的后一个节点
            Node second = first.next;
            // 将反转后的链表开头连接到当前链表的后面
            first.next = reverse;
            // 刷新当前的反转链表开头
            reverse = first;
            // 当前链表的第二个节点变成首部节点
            first = second;
        }
        return reverse;
    }

    /**
     * 递归解法
     * @param first
     * @return
     */
    public Node reverse2(Node first) {
        // 空节点的情况
        if (first == null) return null;
        // 只有一个节点的情况，直接返回当前节点
        if (first.next == null) return first;
        // 获取第二个节点
        Node second = first.next;
        // 先递归颠倒最后 N-1 个结点，然后将原链表中的首结点插入到结果链表的尾端
        Node rest = reverse2(second);
        second.next = first;
        first.next = null;
        return rest;
    }

    public static void main(String[] args) {

    }

}
